#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""
search in rotated array

q159 : find rotated min
"""

class Solution:
    """
    @param A: an integer rotated sorted array
    @param target: an integer to be searched
    @return: an integer
    """
    def search(self, A, target):
        if not A:
            return False

        min_idx = self.find_min_idx(A)

        exist_idx1 = self.search_interval(A, target, 0, min_idx-1)
        if exist_idx1 == -1:
            return self.search_interval(A, target, min_idx, len(A)-1)
        else:
            return exist_idx1

    def search_interval(self, A, target, left, right):
        if not A:
            return -1

        while left <= right:
            medium = (left + right) // 2
            med_v = A[medium]
            if target == med_v:
                return medium

            if target > med_v:
                left = medium + 1
            else:
                right = medium - 1

        return -1

    # def find_min_idx(self, nums):
    #     # write your code here
    #     if not nums:
    #         return -1

    #     left, right = 0, len(nums) - 1
    #     while left < right:
    #         mid = (left + right) // 2
    #         # print(left, mid, right)
    #         if nums[mid] > nums[right]:
    #             left = mid + 1
    #         elif nums[mid] <= nums[right]:
    #             right = mid

    #     return right

    def find_min_idx(self, nums):
        if not nums:
            return -1
        idx, value = self.rec_find(nums, 0, len(nums) - 1)
        return idx

    def rec_find(self, nums, left, right):
        assert left <= right
        if left == right:
            return left, nums[left]

        mid = (left + right) // 2
        print(left, mid, right)
        if nums[mid] > nums[right]:
            left = mid + 1
        elif nums[mid] < nums[right]:
            right = mid
        else:
            assert nums[mid] == nums[right]
            if nums[mid] != nums[left]:
                assert nums[mid] < nums[left]
                right = mid
            else:
                idx1, value1 = self.rec_find(nums, left, mid)
                idx2, value2 = self.rec_find(nums, mid+1, right)
                if value1 > value2:
                    return idx2, value2
                else:
                    return idx1, value1

        return self.rec_find(nums, left, right)


def main():
    print("start main")
    s = Solution()
    ret = s.search([4, 5, 1, 2, 3], 4)
    print(ret)

if __name__ == "__main__":
    main()
